/*
 * @lc app=leetcode.cn id=450 lang=javascript
 *
 * [450] 删除二叉搜索树中的节点
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
  if (root == null) return root

  if (root.val > key) {
    // 往左子树找
    root.left = deleteNode(root.left, key)
  } else if (root.val < key) {
    // 往右子树找
    root.right = deleteNode(root.right, key)
  } else {
    // 找到了
    if (!root.left && !root.right) {
      // 待删除的节点左右子树均为空。证明是叶子节点，直接删除即可
      root = null
    } else if (root.left && !root.right) {
      // 待删除的节点右子树为空，让待删除节点的左子树替代自己。
      root = root.left
    } else if (!root.left && root.right) {
      // 待删除的节点左子树为空，让待删除节点的右子树替代自己。
      root = root.right
    } else if (root.left && root.right) {
      // 如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点（前驱）来替换自己
      let last = root.left
      while (last.right) {
        last = last.right
      }
      // 最终的last就是比当前节点小的最大节点，将值进行替换
      root.val = last.val
      // 删除该最大节点
      root.left = deleteNode(root.left, last.val)
    }
  }
  return root
}
// @lc code=end

// class Node {
//   constructor(val) {
//     this.val = val
//     this.left = this.right = undefined
//   }
// }
// class TreeNode {
//   constructor() {
//     this.root = null
//   }
//   serialize(tree) {
//     const res = []
//     const queue = [tree]
//     while (queue.length > 0) {
//       let node = queue.shift()
//       if (node) {
//         queue.push(node.left)
//         queue.push(node.right)
//         res.push(node.val)
//       } else {
//         res.push(null)
//       }
//     }
//     console.log(res)
//   }
//   create(arr) {
//     this.root = new Node(arr[0])
//     arr.shift()

//     const queue = [this.root]
//     while (queue.length > 0) {
//       let node = queue.shift()
//       // 第一个是左节点，节点为空，直接跳过
//       let leftVal = arr.shift()
//       if (leftVal != null) {
//         node.left = new Node(leftVal)
//         queue.push(node.left)
//       }
//       // 第二个是右节点，节点为空，直接跳过
//       let rightVal = arr.shift()
//       if (rightVal != null) {
//         node.right = new Node(rightVal)
//         queue.push(node.right)
//       }
//       // console.log(queue)
//     }

//     return this.root
//   }
// }
// const treeNode = new TreeNode()
// const tree = treeNode.create([5, 3, 6, 2, 4, null, 7]) // false
// console.log(deleteNode(tree, 5))
